1566E - Buds Re-hanging - CodeForces Solution

//
//  Created by Henry Cafaro
//  Copyright © 2020 Henry Cafaro. All rights reserved.
//

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <random>

using namespace std;

// === Debug macro starts here ===

int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}

#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v);
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
	return os<<"{"<<p.first<<", "<<p.second<<"}";
}
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
	os<<"[";
	for(auto& x:v){os<<x<<", ";}
	return os<<"]";
}


// === Debug macro ends here ===

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

vector<vi> adj;

vector<int> bundles;

int dfs(int x, int p){
    int ct = 0;

    for(auto nxt : adj[x]){
        if(nxt == p)
            continue;
        auto val = dfs(nxt, x);

        if(val == 0){
            // gone
        } else if(val == 1){
            ct++;
        }
    }

    if(ct){
        bundles.push_back(ct);
        return 0;
    } else {
        return 1;
    }

}

void solve(){
    int n;

    cin >> n;

    adj.assign(n, {});

    for(int i = 0; i < n-1; i++){
        int u,v;
        cin >> u >> v;
        u--;v--;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    bundles.clear();

    dfs(0, -1);

    dbg(bundles);

    int ans = 0;

    for(auto x : bundles)
        ans += x;

    ans -= sz(bundles)-1;

    cout << ans << "\n";



    
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
        
    int t;
    cin >> t;
    while(t--) solve();
   
    
    
    
    
    
    
    
    
    
    
}